# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:return True
        length = 0
        tmp = head
        while tmp:
            tmp = tmp.next
            length+=1
        if length==1:return True
        tmp0 = head
        last = None
        for _ in range(length//2-1):
            next = tmp0.next
            tmp0.next = last
            last = tmp0
            tmp0 = next
        tmp1 = tmp0.next
        tmp0.next = last
        if length%2==1:tmp1 = tmp1.next
        while tmp0 and tmp1 and tmp0.val==tmp1.val:
            tmp0, tmp1 = tmp0.next, tmp1.next
        return not tmp0 and not tmp1

head = ListNode(1)
tmp = head
tmp.next = ListNode(2)
tmp = tmp.next
tmp.next = ListNode(1)

print(Solution().isPalindrome(head))
